class Node {
  constructor(element) {
    this.element = element; // 节点的数据域
    this.prev = null; // 节点的指针域
    this.next = null; // 节点的指针域
  }
}
class SingleList extends Node {
  constructor() {
    super();
    this.size = 0; // 单链表的长度
    this.head = new Node("head"); // 表头节点
    this.currNode = ""; // 当前节点的指向
  }

  //在单链表中寻找item元素
  find(item) {
    let currNode = this.head;
    while (currNode && currNode.element !== item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 向单链表中插入元素
  insert(item, element) {
    // 先查找插入时的参考元素是否存在
    let itemNode = this.find(item);
    if (!itemNode) {
      // 如果不存在，则不处理
      return;
    }
    let newNode = new Node(element);
    newNode.next = itemNode.next;
    itemNode.next = newNode;
    this.size++;
  }

  // 在单链表中删除一个节点
  remove(item) {
    // 元素在链表中不存在
    let itemNode = this.find(item);
    if (!itemNode) {
      return;
    }
    // 删除head节点
    if (item === "head") {
      if (!this.isEmpty()) {
        // this.head = this.head.next;
        return;
      } else {
        this.head.next = null;
        return;
      }
    }
    let currNode = this.head;
    while (currNode.next.element !== item) {
      if (!currNode.next) {
        // 所有节点下一个节点都不存在，说明删除的节点不存在
        return;
      }
      currNode = currNode.next;
    }
    currNode.next = currNode.next.next;
    this.size--;
  }

  // 在单链表的尾部添加元素
  append(element) {
    let lastNode = this.findLast();
    let newNode = new Node(element);
    lastNode.next = newNode;
    this.size++;
  }

  // 获取单链表的最后一个节点
  findLast() {
    let currNode = this.head;
    while (currNode.next) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 判断单链表是否为空
  isEmpty() {
    return this.size === 0;
  }
  // 显示当前节点
  show() {
    console.log(this.currNode.element);
  }
  // 获取单链表的长度
  getLength() {
    return this.size;
  }

  // 从当前节点向前移动n个位置, 当前位置默认为头节点
  advance(n, currNode = this.head) {
    this.currNode = currNode;
    while (n-- && this.currNode.next) {
      this.currNode = this.currNode.next;
    }
    return this.currNode;
  }

  // 单链表的遍历显示
  display() {
    let description = "";
    let currNode = this.head;
    while (currNode) {
      description += currNode.element;
      currNode = currNode.next;
      if (currNode) {
        description += "->";
      }
    }
    console.log(description);
  }
  // 清空单链表
  clear() {
    this.head.next = null;
    this.size = 0;
  }
  reverseList() {
    const reverse = (head) => {
      // 如果是空或者只有一个数据时
      if (head === null || head.next === null) return head;
      // 对head的下一个元素进行递归操作
      let newHead = reverse(head.next);
      // 重新设置head元素，将head.next【第二个元素】的next赋值给head
      head.next.next = head;
      // 将head的next设置为空，这样就进行了两个元素的翻转
      head.next = null;
      return newHead;
    };
    this.head = reverse(this.head);
    return this.head;
  }
  // 使用while循环，非递归
  reverseList1() {
    // 获取原链表的头部数据
    let oldHead = this.head;
    if (oldHead === null || oldHead.next === null) return oldHead;
    let newHead = null;
    while (oldHead !== null) {
      // 先把原来链的head下一个数据暂存起来
      let temp = oldHead.next;
      oldHead.next = newHead;
      newHead = oldHead;
      oldHead = temp;
    }
    this.head = newHead;
    return this.head;
  }
}

/* 单向链表测试
let myList = new SingleList();
let arr = [3, 4, 5, 6, 7, 8, 9];

for (let i = 0; i < arr.length; i++) {
  myList.append(arr[i]);
}
myList.display(); // head->3->4->5->6->7->8->9

console.log(myList.find(4));  // Node {data: 4, prev: null, next: Node}

myList.insert(9, 9.1);
myList.insert(3, 3.1);
myList.display();  // head->3->3.1->4->5->6->7->8->9->9.1

myList.remove(9.1);
myList.remove(3);
myList.display();  // head->3.1->4->5->6->7->8->9

console.log(myList.findLast());  // Node {data: 9, prev: null, next: null}

console.log(myList.advance(4));  // Node {data: 6, prev: null, next: Node}

console.log(myList.getLength());  // 7

myList.clear();
myList.display();  // head */

module.exports = { Node, SingleList };
